package hungary;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Set;

// 匈牙利算法解分配问题
public class Hungary {
    // 因为解的个数不确定，所以需要找一个可变的容器来存储解（人员，任务）
    public static ArrayList<HashMap<Integer, Integer>> solution = new ArrayList<>();

    public static void main(String[] args) throws IOException, InterruptedException {
        Problem p = input();
        zeroOut(p);
        System.out.println("-----------------初始矩阵消零-----------------");
        show(p.getCost());
        circle_zero(p);
        // 输出解
        System.out.println("********************* 输出解 *********************");
        for (int l = 0; l < solution.size(); l++) {
            Set<Integer> integers = solution.get(l).keySet();
            System.out.print("解：");
            for (Integer s : integers) {
                System.out.print("<" + s + ", " + solution.get(l).get(s) + "> ");
            }
            System.out.println();
        }
    }

    // 此方法供分支定界方法调用时使用
    public static ArrayList<HashMap<Integer, Integer>> exeHungary(int[][] dis) throws InterruptedException {
        // 转化为求解的问题对象
        int[][] newDis = new int[dis.length + 1][dis.length + 1];
        for (int i = 0; i <= dis.length; i++) {
            newDis[i][0] = 0;
            newDis[0][i] = 0;
        }
        for (int i = 1; i <= dis.length; i++) {
            for (int j = 1; j <= dis.length; j++) {
                newDis[i][j] = dis[i - 1][j - 1];
            }
        }
        Problem p = new Problem(newDis);

        // 执行匈牙利算法
        solution.clear();
        zeroOut(p);
        circle_zero(p);

        return solution;
    }

    // 输入算例到Problem的对象p中
    public static Problem input() throws IOException {
        String line = "";
        String str[];
        int n;
        int[][] cost;
        BufferedReader br = new BufferedReader(new FileReader("src//data//hungary6.txt"));
        line = br.readLine();
        n = Integer.parseInt(line);
        System.out.println("点个数：" + n);
        cost = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            cost[i][0] = 0;
            cost[0][i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            line = br.readLine();
            str = line.split("\\s");
            for (int j = 1; j <= n; j++) {
                cost[i][j] = Integer.parseInt(str[j - 1]);
                System.out.print(cost[i][j] + " ");
            }
            System.out.println();
        }
        return new Problem(cost);
    }

    // 行列减去最小值
    public static void zeroOut(Problem p) {
        int tmp;
        // 减去每一行的最小元素
        for (int i = 1; i <= p.getN(); i++) {
            // 找出本行的最小元素
            tmp = p.getCost()[i][1];
            for (int j = 2; j <= p.getN(); j++) {
                if (p.getCost()[i][j] < tmp) {
                    tmp = p.getCost()[i][j];
                }
            }
            // 本行减去最小元素
            for (int j = 1; j <= p.getN(); j++) {
                p.getCost()[i][j] -= tmp;
            }
        }

        // 减去每一列的最小元素
        for (int j = 1; j <= p.getN(); j++) {
            // 找出本列的最小元素
            tmp = p.getCost()[1][j];
            for (int i = 2; i <= p.getN(); i++) {
                if (p.getCost()[i][j] < tmp) {
                    tmp = p.getCost()[i][j];
                }
            }
            // 本列减去最小元素
            for (int i = 1; i <= p.getN(); i++) {
                p.getCost()[i][j] -= tmp;
            }
        }
    }

    // 圈出单行单列的零元素
    public static void circle_zero(Problem problem) throws InterruptedException {
        int i, j, p;
        // 1.在矩阵外围增加一圈，用来标记每行每列零元素的个数
        for (i = 0; i <= problem.getN(); i++) {
            problem.getCost()[i][0] = 0; // 行
            problem.getCost()[0][i] = 0; // 列
        }

        // 2.标记零元素的个数
        for (i = 1; i <= problem.getN(); i++) {
            for (j = 1; j <= problem.getN(); j++) {
                if (problem.getCost()[i][j] == 0) {
                    problem.getCost()[0][0]++;
                    problem.getCost()[i][0]++;
                    problem.getCost()[0][j]++;
                }
            }
        }

        // 3.初始化零元素的矩阵
        for (i = 0; i <= problem.getN(); i++) {
            for (j = 0; j <= problem.getN(); j++) {
                problem.getZero()[i][j] = 0;
            }
        }

        // 4.圈出所有的独立零元素（直到所有的单零元素的行或列都已经遍历完，只能剩下无零的行或列，或者有多个零的行或列）
        int flag = problem.getCost()[0][0] + 1; // +1就是为了能够在任何情况下都进入while循环
        while (problem.getCost()[0][0] < flag) {
            // 最后判断 cost[0][0]与flag的大小是为了得知，本次循环是否圈中或划去了零元素
            flag = problem.getCost()[0][0];
            // 先行后列，圈中独立零元素
            for (i = 1; i <= problem.getN(); i++) {
                // 找出只有一个零元素的行：i
                if (problem.getCost()[i][0] == 1) {
                    // 1.找出这个零元素所在的列：j，此时得到了（i，j），这个独立零元素的位置
                    for (j = 1; j <= problem.getN(); j++) {
                        if (problem.getCost()[i][j] == 0 && problem.getZero()[i][j] == 0) break;
                    }

                    // 2.圈中这个零元素，更改记录中零元素的个数
                    problem.getZero()[i][j] = 1;
                    problem.getCost()[i][0]--;
                    problem.getCost()[0][j]--;
                    problem.getCost()[0][0]--;

                    // 3.划去这个独立零元素所在列的其他零元素
                    if (problem.getCost()[0][j] > 0) {
                        for (p = 1; p <= problem.getN(); p++) {
                            if (problem.getCost()[p][j] == 0 && problem.getZero()[p][j] == 0) {
                                problem.getZero()[p][j] = 2; // 划去
                                problem.getCost()[p][0]--;
                                problem.getCost()[0][j]--;
                                problem.getCost()[0][0]--;
                            }
                        }
                    }
                }
            }
            // 先列后行，圈中独立零元素
            for (j = 1; j <= problem.getN(); j++) {
                // 只有一个零元素的列j
                if (problem.getCost()[0][j] == 1) {
                    // 1.找出此零元素所在的行i，得到了其坐标（i,j）
                    for (i = 1; i <= problem.getN(); i++) {
                        if (problem.getCost()[i][j] == 0 && problem.getZero()[i][j] == 0) break;
                    }

                    // 2.圈中这个零元素
                    problem.getZero()[i][j] = 1;
                    problem.getCost()[0][j]--;
                    problem.getCost()[i][0]--;
                    problem.getCost()[0][0]--;

                    // 3.划去本行中其他零元素
                    if (problem.getCost()[i][0] > 0) {
                        for (p = 1; p <= problem.getN(); p++) {
                            if (problem.getCost()[i][p] == 0 && problem.getZero()[i][p] == 0) {
                                problem.getZero()[i][p] = 2;
                                problem.getCost()[i][0]--;
                                problem.getCost()[0][p]--;
                                problem.getCost()[0][0]--;
                            }
                        }
                    }
                }
            }
        }

        // 5.如果还有零元素（说明此时应该是出现回路了，有多个解），就圈出行列两个以上的零元素，然后进行判断
        if (problem.getCost()[0][0] > 0) {
            two_zero(problem);
        } else {
            judge(problem);
        }
    }

    // 如果出现了回路，则执行此方法（两个以上的行或列有多个零元素）这里面有递归
    public static void two_zero(Problem p) throws InterruptedException {
        int i, j;
        int k, l;
        int m;
        int flag;
        Problem backup;

        // 1.找出有零元素的行 i
        for (i = 1; i <= p.getN(); i++) {
            if (p.getCost()[i][0] > 0) break;
        }
        // 2.找到此零元素所在的列 j
        if (i <= p.getN()) {
            for (j = 1; j <= p.getN(); j++) {
                // 进行备份一次，用于求解多个解
                backup = new Problem(p);
                if (p.getCost()[i][j] == 0 && p.getZero()[i][j] == 0) {
                    // System.out.println("第"+i+"行，第"+j+"列");
                    // 2.1 圈中一个零 (i,j)
                    p.getZero()[i][j] = 1;
                    p.getCost()[i][0]--;
                    p.getCost()[0][j]--;
                    p.getCost()[0][0]--;

                    // 2.2 将本列中剩下的零划去 j
                    for (k = 1; k <= p.getN(); k++) {
                        if (p.getCost()[k][j] == 0 && p.getZero()[k][j] == 0) {
                            p.getZero()[k][j] = 2;
                            p.getCost()[k][0]--;
                            p.getCost()[0][j]--;
                            p.getCost()[0][0]--;
                        }
                    }

                    // 2.3 将当前元素所在行的其他元素划掉 i
                    for (k = 1; k <= p.getN(); k++) {
                        if (p.getCost()[i][k] == 0 && p.getZero()[i][k] == 0) {
                            p.getZero()[i][k] = 2;
                            p.getCost()[i][0]--;
                            p.getCost()[0][k]--;
                            p.getCost()[0][0]--;
                        }
                    }

                    // 2.4 对剩下的零元素，进行指派分配
                    flag = p.getCost()[0][0] + 1;
                    while (p.getCost()[0][0] < flag) {
                        flag = p.getCost()[0][0];
                        // 先行后列（这里从i+1开始，因为i行的元素已经操作过了）
                        for (k = i + 1; k <= p.getN(); k++) {
                            // 找独立零元素所在的行：k
                            if (p.getCost()[k][0] == 1) {
                                // 圈中行中的独立零元素
                                for (l = 1; l <= p.getN(); l++) {
                                    // 找到独立零元素所在的列：l（得到其坐标 [k,l]）
                                    if (p.getCost()[k][l] == 0 && p.getZero()[k][l] == 0) break;
                                }
                                //System.out.println("<"+k+","+l+">");
                                p.getZero()[k][l] = 1; // 圈中这个零元素
                                p.getCost()[k][0]--;
                                p.getCost()[0][l]--;
                                p.getCost()[0][0]--;
                                // 划去 l 列中的其他零元素
                                for (m = 1; m <= p.getN(); m++) {
                                    if (p.getCost()[m][l] == 0 && p.getZero()[m][l] == 0) {
                                        p.getZero()[m][l] = 2;
                                        p.getCost()[0][l]--;
                                        p.getCost()[m][0]--;
                                        p.getCost()[0][0]--;
                                    }
                                }
                            }
                        }
                        // 先列后行
                        for (l = 1; l <= p.getN(); l++) {
                            // 找到独立零元素所在的列：l
                            if (p.getCost()[0][l] == 1) {
                                // 圈中列中的独立零元素
                                for (k = 1; k <= p.getN(); k++) {
                                    // 找到独立零元素所在的行：k（得到坐标 [k,l]）
                                    if (p.getCost()[k][l] == 0 && p.getZero()[k][l] == 0) break;
                                }
                                p.getZero()[k][l] = 1;
                                p.getCost()[0][l]--;
                                p.getCost()[k][0]--;
                                p.getCost()[0][0]--;
                                // 划去行中的零元素
                                for (m = 1; m <= p.getN(); m++) {
                                    if (p.getCost()[k][m] == 0 && p.getZero()[k][m] == 0) {
                                        p.getZero()[k][m] = 2;
                                        p.getCost()[0][m]--;
                                        p.getCost()[k][0]--;
                                        p.getCost()[0][0]--;
                                    }
                                }
                            }
                        }
                    }

                    // 2.5 如果还有零元素存在，则说明还存在回路，就应该继续 two_zero操作；
                    // 如果没有零元素存在了，应该检验是否得到指派问题的解，如果没有得到解，需要对矩阵进行变换
                    if (p.getCost()[0][0] > 0) {
                        two_zero(p);
                    } else {
                        judge(p);
                    }
                }
                p = backup;
            }
        }
    }

    // 判断是否符合匈牙利算法的条件，也就是矩阵中零元素能否完成一次指派。否则还要对矩阵变换
    public static void judge(Problem p) throws InterruptedException {
        int num = 0; // 解中独立零元素的个数
        int i, j, k;
        HashMap<Integer, Integer> h = new HashMap<>(); // 用来表示一个解
        // 计算矩阵中独立零元素的个数
        for (i = 1; i <= p.getN(); i++) {
            for (j = 1; j <= p.getN(); j++) {
                if (p.getZero()[i][j] == 1) num++;
            }
        }
        // 如果已经找到了一个可行解，就将此可行解添加到解集合中
        if (num == p.getN()) {
            for (k = 1; k <= p.getN(); k++) { // 行
                for (j = 1; j <= p.getN(); j++) { // 列
                    if (p.getZero()[k][j] == 1) {
                        h.put(k, j);
                    }
                }
            }
            solution.add(h);
            // 输出解
            System.out.println("********************* 输出解 *********************");
            System.out.println("找到一个可行解：");
            show(p.getZero());
        } else { // 如果没有可行解
            refresh(p);
        }
    }

    // 矩阵变换（划线，减去最小元素）
    public static void refresh(Problem p) throws InterruptedException {
        int i, j, min = Integer.MAX_VALUE;
        boolean flag1 = true, flag2 = true;
        // 1.标记出所有有零元素的行（以此来对没有零元素的行打勾）
        for (i = 1; i <= p.getN(); i++) {
            for (j = 1; j <= p.getN(); j++) {
                if (p.getZero()[i][j] == 1) {
                    p.getZero()[i][0] = 1;
                    break;
                }
            }
        }

        // 2.打勾，覆盖所有的零元素（2表示此行或者此列打勾）
        while (flag1) {
            flag1 = false;
            // 对没有独立0元素的行打勾，找出这些行中被划去0元素所在的列
            for (i = 1; i <= p.getN(); i++) {
                if (p.getZero()[i][0] == 0) {
                    p.getZero()[i][0] = 2; // 没有独立零元素的行打勾
                    for (j = 1; j <= p.getN(); j++) {
                        if (p.getZero()[i][j] == 2 && p.getZero()[0][j] != 2) {
                            p.getZero()[0][j] = 1; // 此行中，划去零元素的列标记为1
                        }
                    }
                }
            }
            // 对此行中划去0元素的列打勾，找出这些列中无独立0元素所在的行，打勾
            for (j = 1; j <= p.getN(); j++) {
                if (p.getZero()[0][j] == 1) {
                    p.getZero()[0][j] = 2; // 对这一列打勾
                    for (i = 1; i <= p.getN(); i++) {
                        if (p.getZero()[i][j] == 1 && p.getZero()[i][0] != 2) {
                            // 对这一列中有独立零元素的行打勾，本应该标记为2，但是如果标记为2就不能返回去进行while循环
                            // 所以将当前打勾的行标记为0，便于下一次打勾
                            p.getZero()[i][0] = 0;
                            flag1 = true; // 以此来判断是否增加了划线
                            //System.out.println("打勾时候跳不出来了");
                        }
                    }
                }
            }
        }

        // 3.寻找未被覆盖的最小值
        for (i = 1; i <= p.getN(); i++) {
            if (p.getZero()[i][0] == 2) { // 打勾的行 = 未划线的列
                for (j = 1; j <= p.getN(); j++) {
                    if (p.getZero()[0][j] != 2) { // 未打勾的列 = 未划线的列
                        if (flag2) {
                            min = p.getCost()[i][j];
                            flag2 = false;
                        } else {
                            if (p.getCost()[i][j] < min) {
                                min = p.getCost()[i][j];
                            }
                        }
                    }
                }
            }
        }

        // 4.未划线的行减去最小值
        for (i = 1; i <= p.getN(); i++) {
            if (p.getZero()[i][0] == 2) {
                for (j = 1; j <= p.getN(); j++) {
                    p.getCost()[i][j] -= min;
                }
            }
        }

        // 5.划线的列加上最小值
        for (j = 1; j <= p.getN(); j++) {
            if (p.getZero()[0][j] == 2) {
                for (i = 1; i <= p.getN(); i++) {
                    p.getCost()[i][j] += min;
                }
            }
        }

        // 6.零元素的矩阵清零
        for (i = 0; i <= p.getN(); i++) {
            for (j = 0; j <= p.getN(); j++) {
                p.getZero()[i][j] = 0;
            }
        }

        // 7.继续画圈求解
        circle_zero(p);
    }

    public static void show(int[][] a) {
        int n = a.length - 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
    }
}